#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

#include "include/tools.hpp"
#include "include/useful_utils.hpp"

using namespace std;

// 前序遍历
void pre_order(TreeNode *root);
// 中序遍历
void in_order(TreeNode *root);
// 后序遍历
void post_order(TreeNode *root);

int main() {
  /*
    """
        1
      2   3
     5 4
     pre_order  : 12543
     in_order   : 52413
     post_order : 54231
    """
  */
  TreeNode node1;
  node1.val = 1;
  TreeNode node2;
  node2.val = 2;
  TreeNode node3;
  node3.val = 3;
  TreeNode node4;
  node4.val = 4;
  TreeNode node5;
  node5.val = 5;
  TreeNode node6;
  node6.val = 6;

  node1.left = &node2;
  node1.right = &node3;
  node2.left = &node5;
  node2.right = &node4;
  node4.left = &node6;
  tools::printTree(&node1);

  pre_order(&node1);
  cout << endl;
  in_order(&node1);
  cout << endl;
  post_order(&node1);
  cout << endl;
  return 0;
}

void pre_order(TreeNode *root) {
  stack<TreeNode *> S;
  TreeNode *node = root;
  vector<int> res;
  cout << "pre_order: ";
  while (node != nullptr || !S.empty()) {
    while (node != nullptr) {
      // my_str += to_string(node->val);
      res.push_back(node->val);
      // cout << node->val << " ";
      S.push(node);
      node = node->left;
    }
    node = S.top();
    node = node->right;
    S.pop();
  }
  for (auto i : res) {
    cout << i << "";
  }
}

void in_order(TreeNode *root) {
  stack<TreeNode *> S;
  TreeNode *node = root;
  cout << "in_order: ";
  vector<int> res;
  while (node != nullptr || !S.empty()) {
    while (node != nullptr) {
      // my_str += to_string(node->val);
      S.push(node);
      node = node->left;
    }
    node = S.top();
    // cout << node->val << " ";
    res.push_back(node->val);
    node = node->right;
    S.pop();
  }
  for (auto i : res) {
    cout << i << "";
  }
}
void post_order(TreeNode *root) {
  stack<TreeNode *> S;
  TreeNode *node = root;
  cout << "post_order: ";
  vector<int> res;
  while (node != nullptr || !S.empty()) {
    while (node != nullptr) {
      // my_str += to_string(node->val);
      res.push_back(node->val);
      S.push(node);
      node = node->right;
    }
    node = S.top();
    // cout << node->val << " ";
    node = node->left;
    S.pop();
  }
  // reverse the vector in origin place.
  // reverse(res.begin(), res.end());
  // cout << res.size() << endl;
  for (int i = int(res.size()) - 1; i >= 0; i--) {
    cout << res[i] << "";
  }
}
